An anonymous authentication signature technique (Anonymous Credential) is a technique with which a user (signatory) who holds an anonymous authentication certificate having a plurality of attributes and a signature key substantiated thereby given by an authorizer can generate a signature for requesting disclosure of a part of the attributes of the anonymous authentication certificate for a document given by using those. The disclosed attribute and the fact that the signature is generated by the signature key based on a given anonymous authentication certificate can only be known from this signature.
In a case where a user rents a rental car, for example, it is possible to disclose only an own attribute of “having a driver's license” to a rental car company as an agency and rent a car while keeping anonymity through signing time information by using the anonymous credential. When there is a circumstance where it becomes necessary to clarify the attribute of the user such as a case where there is an accident or a crime committed by the rental car rented by the user, it is possible to specify the attribute of the user by making an inquiry to the agency or the authorizer (e.g., the police or a public safety commission).
The user is sensitive for leaks of personal information and the like, so that the user tries to keep the personal information disclosed to the agency to be as small as possible. Further, the agency tries to keep the amount of the personal information of the user to be held as small as possible, since the cost for managing the personal information is increased. Thus, the anonymous authentication technique is expected as a way to be able to provide a personal information using method effective for both the users and the agencies.
Non-Patent Document 1 discloses Camenisch-Lysyanskaya signature that is one of the techniques for achieving such anonymous authentication signature. It is assumed here that attributes allotted to each user are χ[1], - - - , χ[n]. A user discloses χ[i1], - - - , χ[im] among those while hiding the remaining attributes χ[j1], - - - , χ[jn-m], and generates signature data anonymously. Note that “n” and “m” are natural numbers, and n>m. Further, “i1” to “im” are set of m pieces of different natural numbers satisfying 1≦i≦n, and “j1” to “jn-m” is a set of n-m pieces of different natural numbers which satisfy 1≦j≦n and are not included in “i1” to “im”.
Each user has an own private key δ and a Camenisch-Lysyanskaya signature (β, E, κ) for attributes χ[1], - - - , χ[n]. Note here that (β, E, κ) is data satisfying a condition shown in a following Expression 1. Ω, Φ, Ψ, H[1], - - - , H[n], N are public information, and N is RSA modulus (RSA=Rivest, Shamir and Adleman).ΩΦδΨβH[1]χ[1] . . . H[n]χ[n]=Eκ mod N  [Expression 1]
The user discloses χ[i1], - - - , χ[im], and generates a knowledge signature text “Signature” showing that the user knows the data (δ, β, χ[j1], - - - , χ[jn-m]) that satisfies the condition shown in Expression 1 described above (a first method).
Other than this, it is also possible to achieve the anonymous credential with a following method. Each user has Camenisch-Lysyanskaya signatures corresponding to each of a plurality of private keys owned by the user oneself. The sets of the private keys and the Camenisch-Lysyanskaya signatures are defined as the Camenisch-Lysyanskaya signatures (β[n], E[n], κ[n]) for the Camenisch-Lysyanskaya signatures (β[1], E[1], κ[1]), - - - (δ, χ[n]) for the private, keys (δ, χ[1]).
The user discloses χ[i1], - - - , χ[im], and generates a knowledge signature text “Signature” showing that the user knows all the Camenisch-Lysyanskaya signatures (β[n], E[n], κ[n]) for the Camenisch-Lysyanskaya signatures (β[1], E[1], κ[1]), - - - (δ, χ[im]) for (δ, χ[i1]) (a second method).
Further, as technical documents related to this, there are following documents. Patent Document 1 discloses a service providing method with which a certificate for certifying that a property is issued via a proper guarantor device, and users can negotiate with each other anonymously by exchanging the certificates. Patent Document 2 discloses a certificate verification system with which a substituted certificate generated by eliminating user's privacy information from a certificate is issued to be used. Patent Document 3 discloses an attribute authentication system with which a received attribute certificate is used by applying modification or encryption thereon, and a server can verify it. Non-Patent Document 2 discloses an example of a signature method similar to the Camenisch-Lysyanskaya signature method.    Patent Document 1: Japanese Unexamined Patent Publication 2001-188757    Patent Document 2: Japanese Unexamined Patent Publication 2005-159463    Patent Document 3: Japanese Unexamined Patent Publication 2008-131058    Non-Patent Document 1: Jan Camenisch, Anna Lysyanskaya: A Signature Scheme with Efficient Protocols. SCN2002: 268-289    Non-Patent Document 2: Jun Furukawa, Hideki Imai: An Efficient Group Signature Scheme from Bilinear Maps. ACISP 2005: 455-467
Regarding the two methods described in BACKGROUND ART, the first method proves the knowledge of the number of pieces of data (δ, β, χ[j1], - - - , χ[jn-m]) proportional to “n-m”. The second method proves the knowledge of the number of pieces of data (β[1], E[1], κ[1]), - - - (β[n], E[n], κ[n]) proportional to “m”.
Both methods are based on RSA, so that the length of the signature is long. Thus, both of the methods require a vast amount of calculations for a single power residue calculation. It is necessary to perform this calculation for the number of pieces of zero-knowledge to be proved. Thus, the number of times of power residue calculations when generating the signature text becomes proportional to “n-m” with the first method and proportional to “m” with the second method. In any case, there is no difference in respect that it is necessary to perform a vast amount of calculations. Further, the structure capable of overcoming this issue is not depicted in Patent Documents 1 to 3 and Non-Patent Documents 1, 2 described above.
An object of the present invention is to provide an anonymous authentication signature system, a user device, a verification device, a signature method, a verification method, and a program therefor, which are capable of performing generation and verification of an anonymous authentication certificate with a smaller amount of calculation by reducing the number of times of power residue calculations when generating a signature text.